//class Solution {
//public:
//    int trap(vector<int>& height) {
//        int ret = 0;
//        int left = 0, right = height.size() - 1, leftMax = 0, rightMax = 0;
//        while (left < right)
//        {
//            if (height[left] < height[right])
//            {
//                leftMax = max(leftMax, height[left]);
//                ret += min(leftMax, height[right]) - height[left];
//                left++;
//            }
//            else
//            {
//                rightMax = max(rightMax, height[right]);
//                ret += min(rightMax, height[left]) - height[right];
//                right--;
//            }
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        for (int end = -1, cur = 0; cur < nums.size(); cur++)
//        {
//            if (nums[cur])
//                swap(nums[++end], nums[cur]);
//        }
//        return;
//    }
//};



//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int ret = 0;
//        for (int left = 0, right = height.size() - 1, prevMax = 0; left < right; )
//        {
//            ret = max(ret, min(height[left], height[right]) * (right - left));
//            if (height[left] <= height[right])
//                left++;
//            else right--;
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums) {
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//        for (int i = nums.size() - 1; i >= 2;)
//        {
//            int target = -nums[i];
//            for (int left = 0, right = i - 1; left < right;)
//            {
//                int sum = nums[left] + nums[right];
//                if (sum > target) right--;
//                else if (sum < target) left++;
//                else
//                {
//                    ret.push_back({ nums[left], nums[right], nums[i] });
//                    left++, right--;
//                    while (left < right && nums[left] == nums[left - 1])
//                        left++;
//                    while (left < right && nums[right] == nums[right + 1])
//                        right++;
//                }
//            }
//            i--;
//            while (i >= 2 && nums[i] == nums[i + 1])
//                i--;
//        }
//        return ret;
//    }
//};



//class Solution {
//public:
//    int longestConsecutive(vector<int>& nums) {
//        unordered_set<int> st(nums.begin(), nums.end());
//        int ret = 0;
//        for (auto num : st)
//        {
//            if (st.count(num - 1))
//                continue;
//            int x = num + 1;
//            while (st.count(x))
//                x++;
//            ret = max(ret, x - num);
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    int longestConsecutive(vector<int>& nums) {
//        if (nums.size() < 2) return nums.size();
//        sort(nums.begin(), nums.end());
//        unordered_map<int, int> hash;
//        hash[0] = 0;
//        int ret = 0;
//        for (int i = 0; i < nums.size(); i++) {
//            hash[nums[i]] = hash[nums[i] - 1] + 1;
//            ret = max(ret, hash[nums[i]]);
//        }
//        return ret;
//    }
//};



//class Solution {
//public:
//    vector<vector<string>> groupAnagrams(vector<string>& strs) {
//        unordered_map<string, vector<string>> hash;
//        for (auto& str : strs)
//        {
//            auto tmp = str;
//            sort(tmp.begin(), tmp.end());
//            hash[tmp].push_back(str);
//        }
//        vector<vector<string>> ret;
//        for (auto& kv : hash)
//            ret.push_back(kv.second);
//        return ret;
//    }
//};


//class Solution {
//public:
//    vector<int> twoSum(vector<int>& nums, int target) {
//        unordered_map<int, int> hash;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            int aim = target - nums[i];
//            if (hash.count(aim))
//                return { hash[aim], i };
//            hash[nums[i]] = i;
//        }
//        return { -1, -1 };
//    }
//};